{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum XOR Sum of Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumXORSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个数组最小的异或值之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数数组 <code>nums1</code> 和 <code>nums2</code> ，它们长度都为 <code>n</code> 。</p>\n",
    "\n",
    "<p>两个数组的 <strong>异或值之和</strong> 为 <code>(nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1])</code> （<strong>下标从 0 开始</strong>）。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>[1,2,3]</code> 和 <code>[3,2,1]</code> 的 <strong>异或值之和</strong> 等于 <code>(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你将 <code>nums2</code> 中的元素重新排列，使得 <strong>异或值之和</strong> <strong>最小</strong> 。</p>\n",
    "\n",
    "<p>请你返回重新排列之后的 <strong>异或值之和</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [1,2], nums2 = [2,3]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>将 <code>nums2</code> 重新排列得到 <code>[3,2] 。</code>\n",
    "异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [1,0,3], nums2 = [5,3,4]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>将 <code>nums2 重新排列得到</code> <code>[5,4,3] 。</code>\n",
    "异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length</code></li>\n",
    "\t<li><code>n == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 14</code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-xor-sum-of-two-arrays](https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-xor-sum-of-two-arrays](https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]\\n[2,3]', '[1,0,3]\\n[5,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 10**8\n",
    "\n",
    "class Edge:\n",
    "    def __init__(self, from_vertex: int, to_vertex: int, capacity: int, cost: int, flow: int) -> None:\n",
    "        self.from_vertex = from_vertex\n",
    "        self.to_vertex = to_vertex\n",
    "        self.capacity = capacity\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "\n",
    "class MinCostMaxFlow:\n",
    "    def __init__(self, total_vertices: int, source: int, sink: int):\n",
    "        self.total_vertices = total_vertices\n",
    "        self.source = source\n",
    "        self.sink = sink\n",
    "        self.edges = []\n",
    "        self.graph = [[] for _ in range(total_vertices)]\n",
    "        self.distances = [INF] * total_vertices\n",
    "        self.flow_values = [0] * total_vertices\n",
    "        self.previous = [-1] * total_vertices\n",
    "\n",
    "    def add_edge(self, from_vertex: int, to_vertex: int, capacity: int, cost: int) -> None:\n",
    "        self.edges.append(Edge(from_vertex, to_vertex, capacity, cost, 0))\n",
    "        self.edges.append(Edge(to_vertex, from_vertex, 0, -cost, 0))\n",
    "        self.graph[from_vertex].append(len(self.edges) - 2)\n",
    "        self.graph[to_vertex].append(len(self.edges) - 1)\n",
    "\n",
    "    def find_augmenting_path(self) -> bool:\n",
    "        self.flow_values = [0] * self.total_vertices\n",
    "        self.previous = [-1] * self.total_vertices\n",
    "        self.distances = [INF] * self.total_vertices\n",
    "        self.distances[self.source] = 0\n",
    "        self.flow_values[self.source] = INF\n",
    "\n",
    "        priority_queue = [(0, self.source)]  # (distance, vertex)\n",
    "\n",
    "        while priority_queue:\n",
    "            dist_u, u = heappop(priority_queue)\n",
    "            if dist_u > self.distances[u]:  # Ignore outdated distances\n",
    "                continue\n",
    "            for edge_index in self.graph[u]:\n",
    "                edge = self.edges[edge_index]\n",
    "                v = edge.to_vertex\n",
    "                if edge.capacity - edge.flow > 0:\n",
    "                    new_distance = self.distances[u] + edge.cost\n",
    "                    if new_distance < self.distances[v]:\n",
    "                        self.distances[v] = new_distance\n",
    "                        self.previous[v] = edge_index\n",
    "                        self.flow_values[v] = min(self.flow_values[u], edge.capacity - edge.flow)\n",
    "                        heappush(priority_queue, (self.distances[v], v))\n",
    "\n",
    "        return self.previous[self.sink] != -1\n",
    "\n",
    "    def compute(self) -> Tuple[int, int]:\n",
    "        max_flow, min_cost = 0, 0\n",
    "        while self.find_augmenting_path():\n",
    "            flow = self.flow_values[self.sink]\n",
    "            max_flow += flow\n",
    "            min_cost += flow * self.distances[self.sink]\n",
    "            current_vertex = self.sink\n",
    "            while current_vertex != self.source:\n",
    "                edge_index = self.previous[current_vertex]\n",
    "                self.edges[edge_index].flow += flow\n",
    "                self.edges[edge_index ^ 1].flow -= flow\n",
    "                current_vertex = self.edges[edge_index].from_vertex\n",
    "        return max_flow, min_cost\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        source = 2 * n\n",
    "        sink = source + 1\n",
    "        network = MinCostMaxFlow(2 * n + 2, source, sink)\n",
    "        \n",
    "        # Connect source to all vertices in nums1\n",
    "        for i in range(n):\n",
    "            network.add_edge(source, i, 1, 0)\n",
    "        \n",
    "        # Connect all pairs of vertices between nums1 and nums2 with cost as their XOR value\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                cost = nums1[i] ^ nums2[j]\n",
    "                network.add_edge(i, j + n, 1, cost)\n",
    "        \n",
    "        # Connect all vertices in nums2 to sink\n",
    "        for i in range(n):\n",
    "            network.add_edge(i + n, sink, 1, 0)\n",
    "        \n",
    "        _, min_cost = network.compute()\n",
    "        return min_cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 10**8\n",
    "\n",
    "class Edge:\n",
    "    def __init__(self, from_vertex: int, to_vertex: int, capacity: int, cost: int, flow: int) -> None:\n",
    "        self.from_vertex = from_vertex\n",
    "        self.to_vertex = to_vertex\n",
    "        self.capacity = capacity\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "\n",
    "class MinCostMaxFlow:\n",
    "    def __init__(self, total_vertices: int, source: int, sink: int):\n",
    "        self.total_vertices = total_vertices\n",
    "        self.source = source\n",
    "        self.sink = sink\n",
    "        self.edges = []\n",
    "        self.graph = [[] for _ in range(total_vertices)]\n",
    "        self.distances = [INF] * total_vertices\n",
    "        self.flow_values = [0] * total_vertices\n",
    "        self.previous = [-1] * total_vertices\n",
    "\n",
    "    def add_edge(self, from_vertex: int, to_vertex: int, capacity: int, cost: int) -> None:\n",
    "        self.edges.append(Edge(from_vertex, to_vertex, capacity, cost, 0))\n",
    "        self.edges.append(Edge(to_vertex, from_vertex, 0, -cost, 0))\n",
    "        self.graph[from_vertex].append(len(self.edges) - 2)\n",
    "        self.graph[to_vertex].append(len(self.edges) - 1)\n",
    "\n",
    "    def find_augmenting_path(self) -> bool:\n",
    "        self.flow_values = [0] * self.total_vertices\n",
    "        self.previous = [-1] * self.total_vertices\n",
    "        self.distances = [INF] * self.total_vertices\n",
    "        self.distances[self.source] = 0\n",
    "        self.flow_values[self.source] = INF\n",
    "\n",
    "        priority_queue = [(0, self.source)]  # (distance, vertex)\n",
    "\n",
    "        while priority_queue:\n",
    "            dist_u, u = heappop(priority_queue)\n",
    "            if dist_u > self.distances[u]:  # Ignore outdated distances\n",
    "                continue\n",
    "            for edge_index in self.graph[u]:\n",
    "                edge = self.edges[edge_index]\n",
    "                v = edge.to_vertex\n",
    "                if edge.capacity - edge.flow > 0:\n",
    "                    new_distance = self.distances[u] + edge.cost\n",
    "                    if new_distance < self.distances[v]:\n",
    "                        self.distances[v] = new_distance\n",
    "                        self.previous[v] = edge_index\n",
    "                        self.flow_values[v] = min(self.flow_values[u], edge.capacity - edge.flow)\n",
    "                        heappush(priority_queue, (self.distances[v], v))\n",
    "\n",
    "        return self.previous[self.sink] != -1\n",
    "\n",
    "    def compute(self) -> Tuple[int, int]:\n",
    "        max_flow, min_cost = 0, 0\n",
    "        while self.find_augmenting_path():\n",
    "            flow = self.flow_values[self.sink]\n",
    "            max_flow += flow\n",
    "            min_cost += flow * self.distances[self.sink]\n",
    "            current_vertex = self.sink\n",
    "            while current_vertex != self.source:\n",
    "                edge_index = self.previous[current_vertex]\n",
    "                self.edges[edge_index].flow += flow\n",
    "                self.edges[edge_index ^ 1].flow -= flow\n",
    "                current_vertex = self.edges[edge_index].from_vertex\n",
    "        return max_flow, min_cost\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        source = 2 * n\n",
    "        sink = source + 1\n",
    "        network = MinCostMaxFlow(2 * n + 2, source, sink)\n",
    "        \n",
    "        # Connect source to all vertices in nums1\n",
    "        for i in range(n):\n",
    "            network.add_edge(source, i, 1, 0)\n",
    "        \n",
    "        # Connect all pairs of vertices between nums1 and nums2 with cost as their XOR value\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                cost = nums1[i] ^ nums2[j]\n",
    "                network.add_edge(i, j + n, 1, cost)\n",
    "        \n",
    "        # Connect all vertices in nums2 to sink\n",
    "        for i in range(n):\n",
    "            network.add_edge(i + n, sink, 1, 0)\n",
    "        \n",
    "        _, min_cost = network.compute()\n",
    "        return min_cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        #我又来做这道题了\n",
    "        #要从头把这头题想出来可真难\n",
    "        #我受不了了\n",
    "\n",
    "        #我们以0表示数未被占用\n",
    "        #1表示数已经被占用\n",
    "        #dp[mask] = min(dp[])\n",
    "        n = len(nums1)\n",
    "        dp = [math.inf] * (1<<n)\n",
    "        dp[0]=0\n",
    "        for mask in range(1,1<<n,1):\n",
    "            k = bin(mask).count('1')\n",
    "            for pos in range(n):\n",
    "                if ((mask>>pos) & 1 == 1):\n",
    "                    dp[mask] = min(dp[mask], dp[mask^(1<<pos)] + (nums1[k-1]^nums2[pos]))\n",
    "                    #print(mask,k,pos,dp,nums1[k-1],nums2[pos])\n",
    "        #print(dp)\n",
    "        return dp[(1<<n)-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums2)\n",
    "        MASK = 1<<n\n",
    "        dp = [inf] * MASK\n",
    "        dp[0] =0\n",
    "\n",
    "        for mask in range(1,MASK):\n",
    "            cnt = mask.bit_count()\n",
    "            for i in range(n):\n",
    "                if (mask>>i) &1 :\n",
    "                    dp[mask] = min(dp[mask],dp[mask^(1<<i)]+(nums2[i]^nums1[cnt-1]))\n",
    "        \n",
    "        return dp[MASK-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = float('inf')\n",
    "        size = len(nums1)\n",
    "        states  = 1 << size\n",
    "        dp = [float('inf') for _ in range(states)]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for state in range(states):\n",
    "            one_cnt = bin(state).count('1')\n",
    "            for i in range(size):\n",
    "               if (state >> i) & 1:\n",
    "                    dp[state] = min(dp[state], dp[state ^ (1 << i)] + (nums1[i] ^ nums2[one_cnt - 1]))\n",
    "        \n",
    "        return dp[states - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        memo = {}\n",
    "        memo[(1 << n)-1] = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            temp = {}\n",
    "            for mask in memo.keys():\n",
    "                for j in range(n):\n",
    "                    if mask & (1 << j) != 0:\n",
    "                        temp[mask ^ (1 << j)] = min(\n",
    "                            temp.get(mask ^ (1 << j), float('inf')), memo[mask] + (nums1[i] ^ nums2[j]))\n",
    "            memo = temp\n",
    "        return memo[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        fls=[1<<n+64 for i in range(1<<(n))]\n",
    "        fls[0]=0\n",
    "        for i in range(0,1<<n):\n",
    "            for k in range(n):\n",
    "                j=i.bit_count()\n",
    "                if (1<<k)&i==0:\n",
    "                    s=(1<<k)+i                    \n",
    "                    fls[s]=min(fls[s],fls[i]+(nums1[j]^nums2[k]))\n",
    "        return fls[-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [[1e9] * (1 << n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][1 << i] = nums1[0] ^ nums2[i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1 << n):\n",
    "                for k in range(n):\n",
    "                    if (j >> k) & 1:\n",
    "                        # print(j - (1 << k), i-1)\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][j - (1 << k)] + (nums1[i] ^ nums2[k]))\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[n-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [[1e9] * (1 << n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][1 << i] = nums1[0] ^ nums2[i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1 << n):\n",
    "                for k in range(n):\n",
    "                    if (j >> k) & 1:\n",
    "                        # print(j - (1 << k), i-1)\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][j - (1 << k)] + (nums1[i] ^ nums2[k]))\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[n-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        u = (1 << n) - 1\n",
    "        f = [0] * (u + 1)\n",
    "        for i, x in enumerate(nums1):\n",
    "            tmp = [inf] * (u + 1)\n",
    "            for sta in range(u, -1, -1):\n",
    "                mask = u ^ sta # 补集\n",
    "                while mask:\n",
    "                    lb = mask & -mask\n",
    "                    j = lb.bit_length() - 1\n",
    "                    tmp[sta] = min(tmp[sta], (x ^ nums2[j]) + f[sta | (1 << j)])\n",
    "                    mask ^= lb\n",
    "            f = tmp[:]\n",
    "        return f[0]\n",
    "        \n",
    "        # @lru_cache(None)\n",
    "        # def dfs(sta, i): # 倒序搜索nums1 与 nums2每未选的数字进行组合\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     x = nums1[i]\n",
    "        #     mask = u ^ sta # 补集\n",
    "        #     ans = inf\n",
    "        #     while mask:\n",
    "        #         lb = mask & -mask\n",
    "        #         j = lb.bit_length() - 1\n",
    "        #         ans = min(ans, (x ^ nums2[j]) + dfs(sta | (1 << j), i - 1))\n",
    "        #         mask ^= lb\n",
    "        #     # for j in range(n):\n",
    "        #     #     if mask >> j & 1:\n",
    "        #     #         ans = min(ans, (x ^ nums2[j]) + dfs(sta | (1 << j), i - 1))\n",
    "        #     return ans\n",
    "        # return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "min_ = lambda a, b: a if a <= b else b\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        m = 1 << n\n",
    "        bitcnt = [0] * m\n",
    "        for i in range(n):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                bitcnt[j | bit] = bitcnt[j] + 1\n",
    "        masks = [[] for _ in range(n+1)]\n",
    "        for ma, c in enumerate(bitcnt):\n",
    "            masks[c].append(ma)\n",
    "\n",
    "        dp = [inf] * m\n",
    "        dp[0] = 0\n",
    "        for i, x in enumerate(nums1):\n",
    "            for ma in masks[i+1]:\n",
    "                base = ma\n",
    "                while ma:\n",
    "                    j = (ma ^ (ma - 1)).bit_count() - 1\n",
    "                    ma &= ma - 1\n",
    "                    dp[base] = min_(dp[base], dp[base ^ (1 << j)] + (x ^ nums2[j]))\n",
    "\n",
    "        return dp[m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        m = 1 << n\n",
    "        bitcnt = [0] * m\n",
    "        for i in range(n):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                bitcnt[j | bit] = bitcnt[j] + 1\n",
    "        masks = [[] for _ in range(n+1)]\n",
    "        for ma, c in enumerate(bitcnt):\n",
    "            masks[c].append(ma)\n",
    "\n",
    "        dp = [inf] * m\n",
    "        dp[0] = 0\n",
    "        for i, x in enumerate(nums1):\n",
    "            for ma in masks[i+1]:\n",
    "                for j in range(n):\n",
    "                    if not ma >> j & 1:\n",
    "                        continue\n",
    "                    dp[ma] = min(dp[ma], dp[ma ^ (1 << j)] + (x ^ nums2[j]))\n",
    "\n",
    "        return dp[m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heappop, heappush\r\n",
    "class Solution:\r\n",
    "    def minimumXORSum(self, nums1: list[int], nums2: list[int]) -> int:\r\n",
    "        # dp[mask] := minimum xor sum of first i nums in nums1 with bitset nums in nums2, i equals to bitset count\r\n",
    "        # dp[0] = 0\r\n",
    "        # dp[mask] = min(dp[mask ^ (1 << j)] + nums1[i - 1] ^ nums2[j])\r\n",
    "        n = len(nums1)\r\n",
    "        m = 1 << n\r\n",
    "        dp = [234881011] * m\r\n",
    "        dp[0] = [0]\r\n",
    "        hq = [(0, 0, 0)]\r\n",
    "        heapify(hq)\r\n",
    "        # dijkstra\r\n",
    "        while True:\r\n",
    "            xsum, mask, i = heappop(hq)\r\n",
    "            if i == n:\r\n",
    "                break\r\n",
    "            for j in range(n):\r\n",
    "                if (mask >> j) & 1: continue\r\n",
    "                nxt = mask | (1 << j)\r\n",
    "                nxt_xsum = xsum + (nums1[i] ^ nums2[j])\r\n",
    "                if dp[nxt] > nxt_xsum:\r\n",
    "                    dp[nxt] = nxt_xsum\r\n",
    "                    heappush(hq, (nxt_xsum, nxt, i + 1))\r\n",
    "        \r\n",
    "        return dp[m - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        # O(2^n * n)\n",
    "        # O(2^n)\n",
    "        \n",
    "        l = len(nums1)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, status):\n",
    "            nonlocal l\n",
    "            if i == l: return 0\n",
    "            \n",
    "            v = float(\"inf\")\n",
    "            for j in range(l):\n",
    "                if (status >> j) & 1:\n",
    "                    sub = status ^ (1 << j)\n",
    "                    v = min(v, dfs(i+1, sub) + (nums2[j] ^ nums1[i]))\n",
    "                    \n",
    "            return v\n",
    "        \n",
    "        \n",
    "        res = dfs(0, (1 << l) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        # 预处理+DP+状态压缩+位运算\r\n",
    "        # dp[i, mask]表示nums1遍历到i, nums2使用mask对应的数字时的最小异或值 (mask的1的数目需要是i+1)\r\n",
    "        # dp[i, mask] = min(dp[i-1, premask] + (nums[i]^nums[j])) (其中mask=premask|(1<<j))\r\n",
    "        n = len(nums1)\r\n",
    "        total = 1 << n\r\n",
    "        dp = [[float(\"inf\")] * total for _ in range(n)]\r\n",
    "        # 提前预处理得到每个mask的1的数目并加入masks字典中, masks[i]存储1的个数为i的所有mask列表\r\n",
    "        masks = [[] for _ in range(n + 1)]\r\n",
    "        ones = [0] * total\r\n",
    "        for mask in range(total):\r\n",
    "            ones[mask] = 0 if mask == 0 else ones[mask & (mask - 1)] + 1\r\n",
    "            masks[ones[mask]].append(mask)\r\n",
    "        # DP部分\r\n",
    "        for i in range(n):\r\n",
    "            for mask in masks[i + 1]:\r\n",
    "                # 注意mask的1的个数是i+1\r\n",
    "                for j in range(n):\r\n",
    "                    if mask & (1 << j):\r\n",
    "                        # 当前mask使用了第j位, 可以将其去掉得到前一个mask\r\n",
    "                        premask = mask ^ (1 << j)\r\n",
    "                        # 然后与当前数字进行异或, 取较小值 (注意i==0的特殊情况)\r\n",
    "                        dp[i][mask] = min(dp[i][mask], (0 if i == 0 else dp[i - 1][premask]) + (nums1[i] ^ nums2[j]))\r\n",
    "        # 最终结果自然是dp[n - 1][total - 1]\r\n",
    "        return dp[n - 1][total - 1]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution(object):\n",
    "    def minimumXORSum(self, nums1, nums2):\n",
    "        n =len(nums1)\n",
    "        st =[(0,0)] # (cost, state)\n",
    "        visited = [0]*(1<<n)\n",
    "        while st:\n",
    "            cost,state = heapq.heappop(st)\n",
    "            if visited[state]:continue\n",
    "            if state == (1<<n)-1:return cost\n",
    "            visited[state] =1\n",
    "            j= bin(state).count('1')\n",
    "            for i in range(n):\n",
    "                if (state >>i &1): continue\n",
    "                newState = state + (1<<i)\n",
    "                if visited[newState]:continue\n",
    "                heapq.heappush(st,(cost+ (nums1[i] ^ nums2[j]),state + (1<<i)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        N=1<<n\n",
    "        dp=[[inf] * N for _ in range(n+1)]\n",
    "        dp[0][0]=0\n",
    "\n",
    "        for i,v in enumerate(nums1):\n",
    "            for j in range(1,N):\n",
    "                if j.bit_count()==i+1:\n",
    "                    for k in range(n):\n",
    "                        if j>>k&1:\n",
    "                            dp[i+1][j]=min(dp[i+1][j],dp[i][j^(1<<k)]+(v^nums2[k]))\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        #^==&~\n",
    "        #优先级+>^\n",
    "        #状态压缩dp\n",
    "        n=len(nums2)\n",
    "        mask=1<<n\n",
    "        f=[[inf]*(mask) for _ in range(n+1)]\n",
    "        f[0][0]=0\n",
    "        for i in range(1,n+1):\n",
    "            for s in range(mask):\n",
    "                if sum([1 for i in range(n) if (s>>i)&1]) != i:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s>>j)&1 == 0 :\n",
    "                        continue\n",
    "                    pre=s^(1<<j)\n",
    "                    f[i][s]=min(f[i][s],f[i-1][pre]+(nums1[i-1]^nums2[j]))\n",
    "        return f[n][mask-1] \n",
    "                \n",
    "        \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "        \r\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        # @cache\r\n",
    "        # def dfs(idx,mask):\r\n",
    "        #     if idx==len(nums2):\r\n",
    "        #         return 0\r\n",
    "        #     res = 2**31-1\r\n",
    "        #     for ii in range(len(nums2)):\r\n",
    "        #         if mask&(1<<ii):\r\n",
    "        #             continue\r\n",
    "        #         mask+=(1<<ii)\r\n",
    "        #         res = min(res,nums1[idx]^nums2[ii]+dfs(idx+1,mask))\r\n",
    "        #         mask-=(1<<ii)\r\n",
    "        #     return res\r\n",
    "        # return dfs(0,0)\r\n",
    "        n = len(nums2)\r\n",
    "        dp = [[1<<31 for ii in range(1<<n)]for jj in range(n+1)]\r\n",
    "        def bitcount(num):\r\n",
    "            ans = 0\r\n",
    "            while num:\r\n",
    "                ans+=1\r\n",
    "                num = num&(num-1)\r\n",
    "            return ans\r\n",
    "        dp[0][0] = 0\r\n",
    "        for ii in range(n):\r\n",
    "            for jj in range(1,1<<n):\r\n",
    "                if bitcount(jj)!=ii+1:\r\n",
    "                    continue\r\n",
    "                for kk in range(n):\r\n",
    "                    if jj&(1<<kk):\r\n",
    "                        dp[ii+1][jj] = min(dp[ii+1][jj],dp[ii][jj-(1<<kk)]+(nums1[ii]^nums2[kk]))\r\n",
    "        return dp[n][(1<<n)-1]\r\n",
    "                \r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        l = len(nums1)\n",
    "        if l == 1:\n",
    "            return nums1[0] ^ nums2[0]\n",
    "        n = 1 << l\n",
    "        states = [[float('inf')] * l for _ in range(n)]\n",
    "\n",
    "        for mask in range(1, n):\n",
    "            cnt = bin(mask).count('1')\n",
    "            for i in range(l):\n",
    "                if mask & (1 << i):\n",
    "                    if cnt > 1:\n",
    "                        states[mask][cnt-1] = min(states[mask][cnt-1], states[mask ^ (1 << i)][cnt-2] + (nums2[i] ^ nums1[cnt-1]))\n",
    "                        # print(mask, cnt, mask ^ (1 << i))\n",
    "                        # print(states[mask ^ (1 << i)][cnt-2], nums2[i] ^ nums1[cnt-1])\n",
    "                        # print(states[mask][cnt-1])\n",
    "                    else:\n",
    "                        states[mask][cnt-1] = min(states[mask][cnt-1], nums2[i] ^ nums1[0])\n",
    "        # print(states)\n",
    "        return states[n-1][l-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        #重新排列使得其异或值之和最小\n",
    "        #异或值总是尽量使得其和越大越好。那么其最大值结果是14!\n",
    "        #利用数位dp，其中nums2中的结果有哪些可用\n",
    "        \n",
    "        # 或者是是利用\n",
    "\n",
    "        def dp(i,status,nums1,nums2,cache):\n",
    "            if i==len(nums1):\n",
    "                return 0\n",
    "            if (i,status) in cache:\n",
    "                return cache[i,status]\n",
    "            ans=10000000000     #需要足够大14*10**7\n",
    "            j=0\n",
    "            num=status\n",
    "            while num:\n",
    "                #1表示可用\n",
    "                if num&1:\n",
    "                    ans=min(ans,dp(i+1,status^(1<<j),nums1,nums2,cache)+(nums1[i]^nums2[j]))\n",
    "                num>>=1\n",
    "                j+=1\n",
    "            cache[i,status]=ans\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dp(0,(1<<len(nums1))-1,nums1,nums2,{})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        def helper(i, mask, memo):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if (i, mask) in memo:\n",
    "                return memo[(i, mask)]\n",
    "            memo[(i, mask)] = float('inf')\n",
    "            for j in range(n):\n",
    "                if ((1 << j) & mask) == 0:\n",
    "                    memo[(i, mask)] = min(memo[(i, mask)], (nums1[i] ^\n",
    "                                          nums2[j])+helper(i+1, mask | (1 << j), memo))\n",
    "            return memo[(i, mask)]\n",
    "        return helper(0, 0, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "bits = [[i for i in range(14) if 1<<i&x] for x in range(1<<14)] \n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1 )\n",
    "        m = 1 << n \n",
    "        m_ = m - 1 \n",
    "        f =  [0]+[inf]*m  \n",
    "        \n",
    "        for x in range(m): \n",
    "            for j in bits[m_ ^ x]:\n",
    "                f[x|1<<j] = min(f[x|1<<j],f[x]+(nums1[x.bit_count()]^nums2[j]) )\n",
    "        return f[m_]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "bits = [[i for i in range(14) if 1<<i&x] for x in range(1<<14)]\n",
    "cnt = [x.bit_count() for x in range(1<<14)]\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1 )\n",
    "        m = 1 << n \n",
    "        m_ = m - 1 \n",
    "        f =  [0]+[inf]*m  \n",
    "        min = lambda x,y:x if x < y else y\n",
    "        for x in range(m): \n",
    "            for j in bits[m_ ^ x]:\n",
    "                f[x|1<<j] = min(f[x|1<<j],f[x]+(nums1[cnt[x]]^nums2[j]) )\n",
    "        return f[m_]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, mask, INF = len(nums1), 1 << len(nums1), inf\n",
    "        f = [[INF] * mask for _ in range(n + 10)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for s in range(mask):\n",
    "                if sum([1 for i in range(n) if (s >> i) & 1]) != i:\n",
    "                    continue\n",
    "                for j in range(1, n + 1):\n",
    "                    if ((s >> (j - 1)) & 1) == 0:\n",
    "                        continue\n",
    "                    f[i][s] = min(f[i][s], f[i - 1][s^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]))\n",
    "        return f[n][mask - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, mask, INF = len(nums1), 1 << len(nums1), 0x3f3f3f3f\n",
    "        f = [[INF] * mask for _ in range(n + 10)]\n",
    "        f[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for s in range(mask):\n",
    "                if sum([1 for i in range(n) if (s >> i) & 1]) != i:\n",
    "                    continue\n",
    "\n",
    "                for j in range(1, n + 1):\n",
    "                    if ((s >> (j - 1)) & 1) == 0:\n",
    "                        continue\n",
    "                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]))\n",
    "        \n",
    "        return f[n][mask - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, mask, INF = len(nums1), 1 << len(nums1), 0x3f3f3f3f\n",
    "        f = [[INF] * mask for _ in range(n + 10)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for s in range(mask):\n",
    "                if sum([1 for i in range(n) if (s >> i) & 1]) != i:\n",
    "                    continue\n",
    "                for j in range(1, n + 1):\n",
    "                    if ((s >> (j - 1)) & 1) == 0:\n",
    "                        continue\n",
    "                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]))\n",
    "        return f[n][mask - 1]\n",
    "\n",
    "# 作者：宫水三叶\n",
    "# 链接：https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/solutions/2402125/gong-shui-san-xie-yi-ti-shuang-jie-zhuan-iusv/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "def bi_encode(indices, bi_code):\n",
    "    for index in indices:\n",
    "        bi_code[index] = '1'\n",
    "    code = ''.join(bi_code)\n",
    "    for index in indices:\n",
    "        bi_code[index] = '0'\n",
    "    return code\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.xor_matrix = {}\n",
    "        self.bi_code = None\n",
    "        self.n = None\n",
    "\n",
    "    def recur(self, indices1, indices2):\n",
    "        if not indices1:\n",
    "            return 0\n",
    "        s1 = bi_encode(indices1, self.bi_code)\n",
    "        s2 = bi_encode(indices2, self.bi_code)\n",
    "        if (s1, s2) in self.xor_matrix:\n",
    "            return self.xor_matrix[(s1, s2)]\n",
    "        ans = 3 * 10 ** 8\n",
    "        for index in range(len(indices1)):\n",
    "            s3 = bi_encode([indices1[index]], self.bi_code)\n",
    "            s4 = bi_encode([indices2[-1]], self.bi_code)\n",
    "            ans = min(ans,\n",
    "                      self.recur(indices1[0:index] + indices1[index + 1:], indices2[:-1]) + self.xor_matrix[(s3, s4)])\n",
    "        self.xor_matrix[(s1, s2)] = ans\n",
    "        return ans\n",
    "\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        self.n = len(nums1)\n",
    "        self.bi_code = ['0'] * self.n\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.n):\n",
    "                s1 = bi_encode([i], self.bi_code)\n",
    "                s2 = bi_encode([j], self.bi_code)\n",
    "                self.xor_matrix[(s1, s2)] = nums1[i] ^ nums2[j]\n",
    "        return self.recur(list(range(self.n)), list(range(self.n)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if state & 1 << i == 0:\n",
    "                    res = min(res, (nums1[idx] ^ nums2[i]) + dfs(idx + 1, state | 1 << i))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        m = 1 << n\n",
    "\n",
    "        f = [[float('inf')] * (n + 1) for _ in range(m)]\n",
    "\n",
    "        f[0][0] = 0\n",
    "\n",
    "        for mask in range(1,m):\n",
    "            up = mask.bit_count()\n",
    "            for i in range(up):\n",
    "                for j in range(n):\n",
    "                    if mask & (1 << j):\n",
    "                        f[mask][i + 1] = min(f[mask][i + 1],f[mask ^ (1 << j)][i] + (nums1[i] ^ nums2[n-1-j]))\n",
    "\n",
    "\n",
    "        return min(f[m - 1])\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, st):\n",
    "            if i == len(nums1):\n",
    "                return 0\n",
    "            mi = inf\n",
    "            for j in range(len(st)):\n",
    "                if not st[j]:\n",
    "                    lst = list(st)\n",
    "                    lst[j] = 1\n",
    "                    d = (nums1[i] ^ nums2[j]) + dp(i + 1, tuple(lst))\n",
    "                    mi = min(mi, d)\n",
    "            return mi\n",
    "\n",
    "        dpa = dp(0, tuple([0] * len(nums2)))\n",
    "\n",
    "        dp.cache_clear()\n",
    "        return dpa\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1, nums2):\n",
    "        n = len(nums1)\n",
    "        q = [(0, 0, 0)]\n",
    "        visited = set()\n",
    "        while q:\n",
    "            cost, i, cur = heappop(q)\n",
    "            if i == n:\n",
    "                return cost\n",
    "            if cur in visited:\n",
    "                continue\n",
    "            visited.add(cur)\n",
    "            for j in range(n):\n",
    "                if cur & 1 << j == 0:\n",
    "                    nxt = cur | 1 << j\n",
    "                    heappush(q, (cost + (nums1[i] ^ nums2[j]), i + 1, nxt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        l = len(nums1)\n",
    "        if l == 1:\n",
    "            return nums1[0] ^ nums2[0]\n",
    "        n = 1 << l\n",
    "        states = [[float('inf')] * l for _ in range(n)]\n",
    "\n",
    "        for mask in range(1, n):\n",
    "            cnt = bin(mask).count('1')\n",
    "            for i in range(l):\n",
    "                if mask & (1 << i):\n",
    "                    if cnt > 1:\n",
    "                        states[mask][cnt-1] = min(states[mask][cnt-1], states[mask ^ (1 << i)][cnt-2] + (nums2[i] ^ nums1[cnt-1]))\n",
    "                        # print(mask, cnt, mask ^ (1 << i))\n",
    "                        # print(states[mask ^ (1 << i)][cnt-2], nums2[i] ^ nums1[cnt-1])\n",
    "                        # print(states[mask][cnt-1])\n",
    "                    else:\n",
    "                        states[mask][cnt-1] = min(states[mask][cnt-1], nums2[i] ^ nums1[0])\n",
    "        print(states)\n",
    "        return states[n-1][l-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #ETL, DFS\n",
    "    # def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "    #     n = len(nums1)\n",
    "    #     @cache\n",
    "    #     def dfs(s1, s2):\n",
    "    #         if s1 == 0:\n",
    "    #             return 0\n",
    "    #         result = float('inf')\n",
    "    #         for i in range(n):\n",
    "    #             for j in range(n):\n",
    "    #                 if ((s1>>i)&1==1) and ((s2 >> j) & 1==1):\n",
    "    #                     result = min(result, (nums1[i]^nums2[j]) + dfs(s1^(1<<i), s2^(1<<j)))\n",
    "    #         return result\n",
    "    #     return dfs(2**n-1, 2**n-1)\n",
    "    # DFS\n",
    "    # def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "    #     n = len(nums1)\n",
    "    #     cache = {}\n",
    "    #     def dfs(i, mask):\n",
    "    #         if i == n:\n",
    "    #             return 0\n",
    "    #         if (i,mask) in cache:\n",
    "    #             return cache[(i,mask)]\n",
    "    #         result = float('inf')\n",
    "    #         for j in range(n):\n",
    "    #             if (mask >> j) & 1 == 1:\n",
    "    #                 result = min(result, (nums1[i] ^ nums2[j]) + dfs(i+1, mask ^ (1 << j)))\n",
    "    #         cache[(i,mask)] = result\n",
    "    #         return result\n",
    "    #     return dfs(0, 2 ** n - 1)\n",
    "\n",
    "    #DP\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [[float('inf')] * (2**n) for _ in range(n+1)]\n",
    "        for j in range(2**n):\n",
    "            dp[0][j] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for mask in range(2**n):\n",
    "                for j in range(n):\n",
    "                    if (mask >> j) & 1 == 1:\n",
    "                        dp[i+1][mask] = min(dp[i+1][mask], (nums1[i]^nums2[j]) + dp[i][mask ^ (1<<j)])\n",
    "        return dp[n][2**n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = 1<<len(nums1)\n",
    "        INF = int(1e9+10)\n",
    "\n",
    "        dp = [[INF for _ in range(n)] for _ in range(len(nums1)+1)]\n",
    "        for i in range(len(nums1)+1):\n",
    "            dp[i][0] =0\n",
    "        for i in range(len(nums1)):\n",
    "            for k in range(len(nums1)):\n",
    "                state = 1<<k\n",
    "                for j in range(n):\n",
    "                    if j & state !=0:\n",
    "                        f = j^ state\n",
    "                        dp[i][j] = min(dp[i-1][f]+ (nums1[i]^nums2[k]),dp[i][j])\n",
    "        return dp[len(nums1)-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums2)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(idx,left):\n",
    "            if idx == len(nums1)-1:\n",
    "                return nums1[idx]^left[0]\n",
    "            ans = float(\"inf\")\n",
    "            for x in left:\n",
    "                tm = list(left)\n",
    "                tm.remove(x)\n",
    "                ans = min(ans,dfs(idx+1,tuple(tm))+(x^nums1[idx]) )\n",
    "            return ans\n",
    "        return dfs(0,tuple(sorted(nums2)))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(idx, vals):\n",
    "#             if idx == len(nums1) - 1:\n",
    "#                 return nums1[idx] ^ vals[0]\n",
    "#             ans = float(\"inf\")\n",
    "#             for val in vals:\n",
    "#                 tp = list(vals)\n",
    "#                 tp.remove(val)\n",
    "#                 ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "#             return ans\n",
    "#         return dfs(0, tuple(sorted(nums2)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tmp = list(vals)\n",
    "                tmp.remove(val)\n",
    "                ans = min(ans, dfs(idx + 1, tuple(tmp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, tuple(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums2.sort()        \n",
    "        @cache\n",
    "        def dfs(res,i):\n",
    "            if i == len(nums1):\n",
    "                return 0\n",
    "            r = []\n",
    "            for j in range(len(res)):\n",
    "                new_res = res[:j]+res[j+1:]\n",
    "                r.append((nums1[i]^res[j]) + dfs(new_res,i+1))\n",
    "            return min(r)\n",
    "        return dfs(tuple(nums2),0)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "\n",
    "        nums2.sort()        \n",
    "        @cache\n",
    "        def dfs(res,i):\n",
    "            #print(cur,res,i,self.ret)\n",
    "            \n",
    "            if i == len(nums1):\n",
    "                return 0\n",
    "            r = []\n",
    "            for j in range(len(res)):\n",
    "                new_res = res[:j]+res[j+1:]\n",
    "                r.append((nums1[i]^res[j]) + dfs(new_res,i+1))\n",
    "\n",
    "            return min(r)\n",
    "        return dfs(tuple(nums2),0)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1, nums2) -> int:\n",
    "        length = len(nums1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, vals):\n",
    "            if idx == length - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float('inf')\n",
    "            for val in vals:\n",
    "                nxt = list(vals)\n",
    "                nxt.remove(val)\n",
    "                nxt=tuple(nxt)\n",
    "                ans = min(ans, dfs(idx + 1, nxt) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, tuple(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(sorted(nums2)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(sorted(nums2)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 回溯爆搜 有状态重叠了 重复没意思 考虑记忆化搜索 14！过不了\n",
    "        # 分割子问题 2^14 可以过\n",
    "        @cache\n",
    "        def dfs(arr):\n",
    "            if len(arr) == 1:\n",
    "                return nums1[-1] ^ arr[0]\n",
    "            ans = 10**9\n",
    "            n = len(arr)\n",
    "            for i in range(n):\n",
    "                ans = min(ans,dfs(arr[:i]+arr[i+1:])+(nums1[-n]^arr[i]))\n",
    "            return ans\n",
    "        return dfs(tuple(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(sorted(nums2)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(sorted(nums2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(nums2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(nums2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, A: List[int], B: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 416 ms ... 77 % ... 23.5 MB ... 25 %\n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        seen = {}\n",
    "        def func(pool):    # 返回 pool 的结果：此处 pool 与 A[-len(pool): ] 配对\n",
    "            if not pool:\n",
    "                return 0\n",
    "            key = tuple(pool)\n",
    "            if key not in seen:\n",
    "                n, res = len(pool), float('inf')\n",
    "                for j in range(n):\n",
    "                    cur = (A[-n] ^ pool[j]) + func(pool[:j] + pool[j+1:])\n",
    "                    res = min(res, cur)\n",
    "                seen[key] = res\n",
    "            return seen[key]\n",
    "        B.sort()\n",
    "        return func(B)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, A: List[int], B: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 320 ms ... 93 % ... 23.5 MB ... 25 %\n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        seen = {}\n",
    "        def func(pool):    # 返回 pool 的结果：此处 pool 与 A[-len(pool): ] 配对\n",
    "            if not pool:\n",
    "                return 0\n",
    "            key = tuple(pool)\n",
    "            if key not in seen:\n",
    "                n, res = len(pool), float('inf')\n",
    "                for j in range(n):\n",
    "                    cur = (A[-n] ^ pool[j]) + func(pool[:j] + pool[j+1:])\n",
    "                    res = min(res, cur)\n",
    "                seen[key] = res\n",
    "            return seen[key]\n",
    "        return func(B)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        res = int(1e12)\n",
    "        xor = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                xor[i][j] = nums1[i] ^ nums2[j]\n",
    "        #@cache\n",
    "        minCost = dict()\n",
    "        def dfs(i, stat, cur):\n",
    "            if cur >= minCost.get(stat,int(1e12)):\n",
    "                return \n",
    "            minCost[stat] = min(cur, minCost.get(stat,int(1e12)))\n",
    "            nonlocal res\n",
    "            if cur >= res:\n",
    "                return\n",
    "            if i == n:\n",
    "                res = min(res, cur)\n",
    "                return \n",
    "            for j in range(n):\n",
    "                if stat >> j & 1 == 0:\n",
    "                    new_stat = stat | (1<<j)\n",
    "                    next_cur = cur + xor[i][j]\n",
    "                    dfs(i+1, new_stat, next_cur)\n",
    "        dfs(0,0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1, nums2) -> int:\n",
    "\n",
    "        @cache\n",
    "        def helper(nums1, nums2):\n",
    "            if len(nums1) == 1:\n",
    "                ans = nums1[0] ^ nums2[0]\n",
    "                return ans\n",
    "            ans = int(1e9)\n",
    "            res = nums1[1:]\n",
    "            for i in range(len(nums2)):\n",
    "                temp = (nums1[0] ^ nums2[i]) + helper(res, nums2[:i] + nums2[i + 1:])\n",
    "                ans = min(ans, temp)\n",
    "            return ans\n",
    "\n",
    "        return helper(tuple(nums1), tuple(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        @cache\n",
    "        def dfs(pos,left):\n",
    "            if pos==n-1:\n",
    "                return nums1[-1]^left[0]\n",
    "            ans=float('inf')\n",
    "            for i in left:\n",
    "                l=list(left)\n",
    "                l.remove(i)\n",
    "                ans=min(ans,(nums1[pos]^i)+dfs(pos+1,tuple(l)))\n",
    "            return ans\n",
    "        return dfs(0,tuple(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, vals):\n",
    "            if idx == len(nums1) - 1:\n",
    "                return nums1[idx] ^ vals[0]\n",
    "            ans = float(\"inf\")\n",
    "            for val in vals:\n",
    "                tp = list(vals)\n",
    "                tp.remove(val)\n",
    "                ans = min(ans, dfs(idx+1,tuple(tp)) + (nums1[idx] ^ val))\n",
    "            return ans\n",
    "        return dfs(0, tuple(sorted(nums2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \"\"\"DP状态压缩\"\"\"\n",
    "        # dp[i][sta]: nums1 前i个数，num2使用情况为sta时，最小XOR sum\n",
    "        # s ^ (1 << j)\n",
    "        n = len(nums1)\n",
    "        dp = [[float('inf') for _ in range(1 << n)] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            dp[0][1 << j] = nums1[0] ^ nums2[j]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for sta in range(1 << n):\n",
    "                if self.get_cnt(sta) != i + 1: continue\n",
    "                for j in range(n):\n",
    "                    # sta 不包含j\n",
    "                    if (sta >> j) & 1 == 0: continue\n",
    "                    dp[i][sta] = min(dp[i][sta], dp[i - 1][sta ^ (1 << j)] + (nums1[i] ^ nums2[j]))\n",
    "        return int(dp[n - 1][(1 << n) - 1])\n",
    "\n",
    "    @staticmethod\n",
    "    def get_cnt(sta: int):\n",
    "        cnt = 0\n",
    "        while sta > 0:\n",
    "            if sta & 1 == 1:\n",
    "                cnt += 1\n",
    "            sta = sta >> 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        target = (1 << n) - 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur: int, state: int) -> int:\n",
    "            if state == target:\n",
    "                return 0\n",
    "            return min(dfs(cur + 1, state | (1 << next)) + (nums1[cur] ^ nums2[next])\n",
    "                for next in range(n) if not state & (1 << next))\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def dfs(used,idx):\n",
    "            if idx >= n: return 0\n",
    "            res = inf\n",
    "            for j in range(n):\n",
    "                if (used >> j) & 1 == 1: continue\n",
    "                res = min(res,(nums2[j]^nums1[idx])+dfs(used|(1<<j),idx+1))\n",
    "            return res\n",
    "        dfs.cache_clear()\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def f(i, mask):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for j in range(n):\n",
    "                if (mask >> j) & 1 > 0:\n",
    "                    continue\n",
    "                p = (nums1[i] ^ nums2[j]) + f(i + 1, mask | (1 << j))\n",
    "                ans = min(ans, p)\n",
    "            return ans\n",
    "\n",
    "        return f(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def dfs(idx, st):\n",
    "            if idx == n: return 0\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if (st>>i)&1: continue\n",
    "                t = nums1[idx]^nums2[i]\n",
    "                p = dfs(idx+1, st|(1<<i))\n",
    "                res = min(res, p+t)\n",
    "                # print(res)\n",
    "            return res\n",
    "        # print(1^3+2^2)\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def back(cur,x):\n",
    "            if cur == n:return 0\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if x&(1<<i):continue\n",
    "                res = min(res,(nums1[cur]^nums2[i])+back(cur+1,x^(1<<i)))\n",
    "            return res\n",
    "        return back(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort()\n",
    "        n = len(nums1)\n",
    "        nn1, nn2, l, r = [], [], n - 1, n - 1\n",
    "        while l >= 0 and r >= 0:\n",
    "            x, y = nums1[l], nums2[r]\n",
    "            if x > y:\n",
    "                nn1.append(x)\n",
    "                l -= 1\n",
    "            elif x < y:\n",
    "                nn2.append(y)\n",
    "                r -= 1\n",
    "            else:\n",
    "                l -= 1\n",
    "                r -= 1\n",
    "        if l >= 0:\n",
    "            nn1 += nums1[l::-1]\n",
    "        else:\n",
    "            nn2 += nums2[r::-1]\n",
    "        n = len(nn1)\n",
    "        rhas = {}\n",
    "        def tb(srt, has):\n",
    "            if srt == n: return 0\n",
    "            key = (srt, has)\n",
    "            if key in rhas: return rhas[key]\n",
    "            v, jd, tep = nn1[srt], 1, float('inf')\n",
    "            for j in range(n):\n",
    "                if has & jd == 0:\n",
    "                    tep = min(tep, tb(srt+1, has|jd) + (nn2[j] ^ v))\n",
    "                jd *= 2\n",
    "            rhas[key] = tep\n",
    "            return tep\n",
    "        tb(0,0)\n",
    "        return tb(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ## dp前i位用了xxx，剩余可选\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def dfs(index, target):\n",
    "            if index == n: return 0\n",
    "            chooses = [i for i in range(n) if (target >> i) & 1 == 0]\n",
    "            ans = 1e12\n",
    "            for next in chooses:\n",
    "                ans = min(ans, dfs(index + 1, target | (1 << next)) + (nums1[index] ^ nums2[next]))\n",
    "            return ans\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        u = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in range(n):\n",
    "                if (i >> k) & 1:\n",
    "                    ans = min(ans, dfs(i ^ (1 << k), j + 1) + (nums1[k] ^ nums2[j]))\n",
    "            return ans\n",
    "        return dfs(u, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(j,st):\n",
    "            if j == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for i,x in enumerate(nums2):\n",
    "                if st >> i & 1:\n",
    "                    ans = min(ans,dfs(j + 1,st ^ (1 << i)) + (nums1[j]^x))\n",
    "            return ans\n",
    "        return dfs(0,(1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        暴力 即找出所有可能排列\n",
    "        但不是 (n!)^2\n",
    "        只需要排列一个数组就行了\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            # 排nums2, state 表示已经选择了某些数, 当前需要结合nums1[i]\n",
    "            if i == n:\n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            for j in range(n):\n",
    "                # 如果j没有被选\n",
    "                if state >> j & 1 == 0:\n",
    "                    # print(i, j, nums1[i] , nums2[j], nums1[i] ^ nums2[j])\n",
    "                    res = min(res, dfs(i+1, state | (1 << j)) + (nums1[i] ^ nums2[j]))\n",
    "                    # print(i, res)\n",
    "            return res\n",
    "        return dfs(0,0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
